package PriorityQueue;

public class UnorderedPriorityQueue<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public UnorderedPriorityQueue(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        arr[size++] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //先找到优先级大的点
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        if (j < size - 1) {
            System.arraycopy(arr,j+1,arr,j,size - 1 - j);
        }
        size--;
        arr[size] = null;
        return ret;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //先找到优先级大的点
        int j = 0;
        for (int i = 1; i < size; i++) {
            if (arr[j].priority() < arr[i].priority()) {
                j = i;
            }
        }
        E ret = (E)arr[j];
        return ret;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}
